package liecai_class.day02;

import java.util.Arrays;
import java.util.Random;

/**
 * 数组的排序:
 * 4.希尔排序
 * 希尔排序是对插入排序的一种改进
 * 插入排序的效率与数组的混乱程度息息相关, 混乱度越高, 需要比较的次数就越多,效率就越低,
 * 对应的, 若数组混乱度低, 则需要比较的次数少, 效率就高
 *
 * 希尔排序的原理是, 想办法降低数组的混乱度,
 * 提升数组的排序效率, 最终以多次高效的比较插入完成排序
 *
 * 定义一个步长, 每隔指定步长取数组中的数, 形成一个组, 将原数组分成若干个组,
 * 再在组内进行插入排序, 保证组内的数据顺序正确,
 * 再进一步降低步长, 重新分组, 对组内进一步排序, 随着步长的缩短, 数组混乱度逐步降低
 * 最终只需要很少的比较和交换, 就可以完成插入排序
 *
 * 希尔排序最初选取比较大的步长, 将数据分为若干组, 此时每个组中数据量少,
 * 虽然数组混乱度高, 但比较的次数少, 随着步长的降低, 虽然每一组的数据量变多了,
 * 但数组的混乱度也明显降低, 所以也只需要很少的比较和排序, 就可以完成排序,
 * 最终步长降到1, 即可完成排序
 *
 * 思考:
 * - 希尔排序一定效率高吗?
 *      不一定, 通常在数组混乱度较高的情况下才会使用,
 *      对于混乱度较低的数组, 直接使用插排效率相对更高
 * - 希尔排序的效率与什么有关?
 *      与数组混乱度有关, 混乱度越高, 希尔排序效率越高
 * - 希尔排序的代码如何实现?
 */
public class ArraySort04 {
    public static void main(String[] args) {
        //生成一个随机数组
        Random rd = new Random();
        int[] arr = new int[10];
        for (int i=0;i<arr.length;i++){
            arr[i] = rd.nextInt(100);
        }
        System.out.println(Arrays.toString(arr));
        /*
            希尔排序
         */
        //外层循环, 控制跨度, 初始长度为数组长度的一半, 每次循环减半, 不能小于1
        for (int gap = arr.length/2;gap>=1;gap/=2){
            //内层循环为依据跨度修改的插入排序
            for (int i=gap;i<arr.length;i++){
                //定义变量, 记录要插入的数据
                int temp = arr[i];
                //从后向前遍历所有已经排好的数据
                //若发现比temp大, 则将其向后移动一位
                //直到发现小于temp或者遍历到首位元素, 则结束循环
                int j=i-gap;
                for (;j>=0&&arr[j]>temp;j-=gap){
                    //将j位置的数据向后移动gap位
                    arr[j+gap] = arr[j];
                }
                //将temp插入j的位置, 注意上面的循环最后一次j-=gap,
                //所以要将temp赋值给arr[j+gap], 完成插入操作
                arr[j+gap] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
